﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0030_FirstBadVersion : IAlgorithm
    {
        // 第一个错误的版本

        // 你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，
        // 所以错误的版本之后的所有版本都是错的。

        // 假设你有 n 个版本[1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。

        // 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。
        // 你应该尽量减少对调用 API 的次数。

        // 提示：
        //  1 <= bad <= n <= 2^31 - 1

        private int bad = 1;
        private bool IsBadVersion(int version)
        {
            return version >= bad;
        }

        public void Test()
        {
            // 算法参数定义
            int n = 2126753390;
            bad = 1702766719;

            // 算法执行与打印
            Console.WriteLine(FirstBadVersion(n));
        }

        // 算法
        // 递归+二分法
        public int FirstBadVersion(int n)
        {
            return FirstBadVersion(1, n);
        }
        private int FirstBadVersion(int s, int e)
        {
            if (s == e)
                return s;
            // 这里有坑，没注意容易超出int界限
            int m = (e - s) / 2 + s;
            if (IsBadVersion(m))
                if (IsBadVersion(m - 1))
                    return FirstBadVersion(s, m - 1);
                else
                    return m;
            else
                return FirstBadVersion(m + 1, e);
        }

        // 循环+二分，差不多，更简洁
        public int FirstBadVersion1(int n)
        {
            int start = 1, end = n;
            while (start < end)
            {
                int mid = (end - start) / 2 + start;
                if (!IsBadVersion(mid))
                    start = mid + 1;
                else
                    end = mid;
            }
            return start;
        }
    }
}
